import java.util.*;


interface Sorter {
	void sort( Comparable [ ] a );
}


class InsertionSort implements Sorter {
    public void sort( Comparable [ ] a ) {

        for( int i = 1; i < a.length; i++ ) {
            Comparable tmp = a[ i ];
			
            int j;
            for(j = i ; j > 0 && tmp.compareTo( a[ j - 1 ] ) < 0; j-- ) {
                a[ j ] = a[ j - 1 ];
			}

            a[ j ] = tmp;
        }
    }
}


class SelectionSort implements Sorter {
    public void sort (Comparable[] a) {

		for (int i = 0; i < a.length-1; i++) {
	    	int min = i;

	    	for (int j = i+1; j < a.length; j++) {

				if (a[j].compareTo(a[min]) < 0) {
		    		min = j;
				}
			}

	    	Comparable tmp = a[min];
	    	a[min] = a[i];
	    	a[i] = tmp;
		}
    }
}


public class Sort {

	static void runSort(Sorter sorter, String sortName) {
		System.out.println(sortName);

		for (int SIZE = 100; SIZE < 25600; SIZE *= 2) {
	    	long start, end;
	    	long elapsed1 = 0, elapsed2 = 0, elapsed3 = 0;
	    	Comparable [ ] a = new Integer [ SIZE ];

			// sorted input
	    	for( int i = 0; i < SIZE; i++ ) {
				a[ i ] = new Integer( i );
			}
	    	start = System.currentTimeMillis();
	    	sorter.sort( a );
	    	end = System.currentTimeMillis();
	    	elapsed1 = end - start;

			// reverse sorted input
		    for( int i = 0; i < SIZE; i++ ) {
				a[ i ] = new Integer( SIZE - i );
			}
	    	start = System.currentTimeMillis();
	    	sorter.sort( a );
	    	end = System.currentTimeMillis();
	    	elapsed2 = end - start;

			// random input
		    Random r = new Random();
		    for( int i = 0; i < SIZE; i++ ) {
				a[ i ] = new Integer( r.nextInt(SIZE) );
			}
		    start = System.currentTimeMillis();
		    sorter.sort( a );
	    	end = System.currentTimeMillis();
		    elapsed3 = end - start;

		    System.out.println("size: " + SIZE + 
							   "\tsorted: " + elapsed1 + 
						       "\treverse: " + elapsed2 + 
							   "\trandom: " + elapsed3);
		}
	}

    public static void main (String[] args) {
		runSort(new InsertionSort(), "Insertion Sort");
		runSort(new SelectionSort(), "Selection Sort");
    }

}